package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 2021/1/1 下午11:15
 */
public class _01_背包问题 {

   public static class Cargo {

        private int weight;
        private int value;

        public Cargo(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }

    }

    public int maxValue(Cargo[] cargos, int maxWeight) {

       return maxValue(cargos,0,maxWeight);
    }

    private int maxValue(Cargo[] cargos,int index, int leave) {

        /**
         * 选到最后了
         */
        if (index >= cargos.length) {

           return 0;
       }


        /**
         * 不选index
         */
        int notSelectvalue = maxValue(cargos,index+1,leave);

        /**
         * 选index
         */
        int selectValue = 0;
        if (leave > cargos[index].weight) {

            /**
             * 能选index
             */
            selectValue = maxValue(cargos,index+1, leave - cargos[index].weight);
            selectValue += cargos[index].value;
        }

        System.out.println("noSelect:" + notSelectvalue + " select:" + selectValue);

        return Math.max(notSelectvalue,selectValue);
    }


}
